#Longest Path Assignment

1 messages · Page 1 of 1 (latest)

left lodge
left lodge
#

hey so i did some things to the code but i cant seem to find the answers

#

this is my latest version but i tried everything and cant help myself anymore

#

thanks for any help

real jackal
#

well, there is many way to address this problem, including using AI and tree navigation, but the easiest answer is to simply try ALL paths 😬

#

Optimization 1: include length of "close loop path" to avoid duplication of calculations

Optimization 2: remove any closed paths that won't resolve

Optimization 3: Use ML to find all possibile exit paths efficiently, then choose longest answer.

Optimization 4: Use ML to find the shortest path, then write this algorithm in reverse 🤣

#

#5. your teacher is crazy.

left lodge
left lodge
#

i improved it a little thanks to chatgpt and it seems to work but i cant find why it doesnt terminate

real jackal
#

You have to "remember" all the paths you took, so I would use recursion for this, when there is more than one choices,
which means you need an Integer[] or VO for memory 🧠

This is really path traversal

#

Both of these solutions forgot to mark visited cells and also forgot to add to "memory"

#

But A* or D* algorithms work pretty well. They use a graph, which you should be able to define from your world definition. (http://en.wikipedia.org/wiki/A*)

Also Dijstra's algorithm should work at finding a path (again uses a graph). It is commonly used for network routing - but it also works for normal path finding. (http://en.wikipedia.org/wiki/Dijkstra's_algorithm)

A*

A* or A star may refer to:

A* search algorithm, a pathfinding algorithm used in computing
A*, the highest grade in examination systems such as the GCE Advanced Level
ASTAR, the Singapore Agency for Science, Technology and Research
AStar, the Eurocopter AS350 Écureuil helicopter
Class A star, a star of spectral class A
Sagittarius A, a radio s...

Dijkstra's algorithm

Dijkstra's algorithm ( DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.The algorithm exists in many variants. Dijkstra's original algorithm found the sho...

#

https://en.wikipedia.org/wiki/A*_search_algorithm

A* search algorithm

A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal.
One major prac...

#

https://en.wikipedia.org/wiki/D*

D*

D* (pronounced "D star") is any one of the following three related incremental search algorithms:

The original D*, by Anthony Stentz, is an informed incremental search algorithm.
Focused D* is an informed incremental heuristic search algorithm by Anthony Stentz that combines ideas of A* and the original D*. Focused D* resulted from a further de...

real jackal