Finding a path faster isn't faster if the path it finds isn't faster than the faster found path.

@m1n3c4rt

6 ай бұрын

this is a sentence

@Me1le

6 ай бұрын

Shouldnt this be "Finding a path faster isn't faster if the path it finds isn't faster than the *slower* found path." or am I misunderstanding?

@beatcomps6349

6 ай бұрын

@@Me1lethe slower path u r referring can be hold as reference path , same as guy is saying it’s just faster , the word faster or slower is just a reference to what u r saying 😂😂😅

@UltraPuppet

6 ай бұрын

en.wikipedia.org/wiki/A*_search_algorithm#Optimality_and_consistency With an appropriate heuristic (in all but pathological cases) A* will not only be faster than Dijkstra's algorithm for point to point traversal, but it will also produce an optimal result. Worth noting is that although Dijkstra's algorithm was designed for point to point mapping, it's a poor choice for that use case - it's a far better fit when you're seeking to calculate path lengths for all possible node pairs in the graph.

@chndrl5649

6 ай бұрын

It all depends on the user. If only the user will be as logical as you...

A* with proper heuristics guarantee shortest path Dijkstra and A* should return same length best path Both examples show that A* implemented incorrectly

@NihongoWakannai

5 ай бұрын

Having inaccurate heuristics is not necessarily a sign of "incorrect" implementation. You cannot always have a perfect distance estimation function without significantly increasing the overall calculation time. With a homogenous grid it's super easy, but if you're working with city streets and potentially traffic data for those streets, there's no way to quickly calculate an accurate distance estimation. A* can still be useful for finding a good path fast, even if it can't guarantee the best one in these situations.

@LarryMcLarren

5 ай бұрын

@@NihongoWakannaiIf the heuristics work s.t. they always cover the best case and no real route can be found which is better than heuristics then yes, A* DOES return the optimal path. A* is used in navigation through cities all the time. Or do you really think your GPS calculates through all the streets in your city? With pathfinding in cities, A* is guaranteed to return the shortest path, no matter how inhomogenous the roads are, if it uses proper heuristics. Virdvird is right, you are wrong.

@NihongoWakannai

5 ай бұрын

@@LarryMcLarren Not with the same speed benefits, when you have to be so pessimistic with the heuristics the calculation time approaches a basic Dijkstra. There are applications where the speed of calculation is more important than the accuracy of the result, that is not an "incorrect" implementation, it's a cost benefit analysis.

@LarryMcLarren

5 ай бұрын

@@NihongoWakannai What you say is generally true, but not in cities as cities do have speedlimits. actually, besides Germany, almost any country has speedlimits and you have a v_max to calculate your optimistic heuristic with. As I said, when navigating through cities, there ALWAYS is a heuristic to find the optimal route regarding driving distance or driving time. In general, you of course are right: If you want to find the cheapest train route, an optimal A* would be Dijkstra, as the only heuristic to be better or equal to each best price is 0.

@rotten-Z

5 ай бұрын

No heuristic is about guarantees

> We programmed A* using a Greedy-Best-First Search Logic just fyi, this means you did not program A*, you programmed a greedy-best-first search. A* is by definition not greedy

A* algorithm always finds shortest path with correct heuristics function.

@blissful4992

5 ай бұрын

It doesn't matter what heuristic you use. A* guarantees the optimal path.

@IceTank

5 ай бұрын

@@blissful4992This is not true. If the heuristic function over estimates the cost of a connection A* can terminate early with a sub optimal path. An optimal path can only be guaranteed if the heuristic function is admissible for a given problem.

@blissful4992

5 ай бұрын

@@IceTank If the heuristic is non admissible (which is what you are explaining) we don’t refer to it as Algorithm A-star, we refer to it as Algorithm A. A-star is a subset of A with an admissible heuristic.

@HypnosisBear

5 ай бұрын

​@@blissful4992exactly 💯

If it doesnt find the shortest path youve implemented A* algorithm wrong. A* algorithm guarantees the shortest path between 2 points.

@anthonymadorsky1551

6 ай бұрын

Hey thanks for the comment! I updated the video description with a short explanation of A*'s behavior in our implementation. Hopefully it clears things up!

@4c6f

6 ай бұрын

​@@anthonymadorsky1551​I appreciate the effort but there is a certain level of changes after which an algorithm starts being a completely different algorithm. Your algorithm is not an A* algorithm since for each potential node A* requires to evaluate both passed distance and estimated distance using a heuristic function which is usually simply euclidian distance. It seems from the video you are only evaluating estimated euclidian distance.

@dhess34

6 ай бұрын

This is content stolen from another channel, so the poster likely has no idea what they’re talking about.

@anthonymadorsky1551

6 ай бұрын

@@dhess34 The content you see is 100% our own. This is my group's final project submission for Data Structures and Algorithms. We are second year computer science students who were asked to create a visualization for, and compare two algorithms that accomplish the same task. Please reach out if you have any questions!

@rescyy2235

6 ай бұрын

​​@@anthonymadorsky1551source code? or your claim is wrong

Nice video, even though its not really a fair race since dijkstra needs no information about the location of the goal but a* does. They are not built to solve the same problem but rather for different scenarios

@blissful4992

5 ай бұрын

A* doesn't necessarily need the location of the goal. You are referring to a specific heuristic (that calculates distance for example) used in tandem with A*. Dijkstra is A* with a uniform heuristic. A* is Dijkstra with admissible heuristics.

@zeroanims4113

5 ай бұрын

@@blissful4992 and what do you think is needed by the heuristic used by A* to calculate distance? exactly, an information about the location of the goal (e.g. coordinates) just like the commenter said.

@blissful4992

5 ай бұрын

@@zeroanims4113 Please go educate yourself on A-star. Distance isn’t necessarily required to make a heuristic for A-star. In a map application scenario you can use: road length, traffic, steepness, narrowness, among other things. A-star doesn’t calculate distance by default. It’s the addition of a heuristic that allows it to do so.

@zeroanims4113

5 ай бұрын

@@blissful4992 and isn't road length, traffic, steepness, narrowness, etc... an extra information required by a*? that's the point of the original comment, and my reply is just another example of extra information a* might use (distance). Again, the only point we're making here is that dijkstra uses no other information, but a* does. Do you agree?

@blissful4992

5 ай бұрын

@@zeroanims4113 No, it’s not required by A*. Actually if you give a heuristic of a constant value to A-star it behaves exactly like Dijkstra. That’s the point and it’s why you’re wrong. Sorry. A-star doesn’t need extra information, it just performs better with it.

You either clearly didn't understand A* or you applied a heuristic that could be greater than the path length(e.g. Manhattan Norm) if you would've applied Euclidean Norm(a heuristic that is always smaller than the length of the shortest path between two points) for example, then a correct implementation would've guaranteed shortest path(equal in length to Dijkstra's)

I love watching these types of videos :D

both may seem viable in this exemple, Dijkstra's may even look better because a few seconds more of calculation might saves you minutes of driving. However keep in mind how they both scale, Djikstra's is kinda like a O(n^2) algorithm while a* is more similar to a O(log(n)) algorithm, if you attempt Dijkstra's algorithm to google map for finding paths across multiple countries or even a few dozen kilometers, you'll soon find out it will take longer to run than you trying to run to the destination by feet... So yeah it would've been fun to add a visualisation of this scaling but it's still a very interesting video, thanks :)

@kang018

6 ай бұрын

big joe notation

@minutenreis

5 ай бұрын

no they just fucked up and did not implement A*, else it should return the shortest path

@thomquiri9860

5 ай бұрын

@@minutenreis idk, a* is a middle ground beetween Dijkstra's and greedy search, you can adjust the heuristics to fit your needs. (but I agree that the "basic" a* do the same result as Djikstra's for a significantly decreased complexity)

@NihongoWakannai

5 ай бұрын

​@@minutenreis A* only returns the shortest path guaranteed if you have a 100% accurate distance estimation to the goal. That is not possible here without a very expensive pre-processing step.

@dmitryburlakov6920

5 ай бұрын

​​​@@NihongoWakannai finally, they come to speak the facts and save the day. I absolutely love how others are saying "just use correct heuristics", leaving the details of "correctness" behind the door. The "correct" heuristics here is a giant lookup table with which you won't even need the algorithm in the first place.

As others said: That's not A* ... you should change the video title before other people get things as wrong as you about those algorithms. The visualization is cool though ;)

Beautifully animated

Astounding!

So what you're saying is you implemented A* incorrectly?

@ritzkid76

2 ай бұрын

ya the path should be identical if they both found the shortest right ?

Amazing!

Very cool!

I came here because the thumbnail of the video looked like the embryo fetus of the xenomorph alien. I was thoroughly disappointed. Then I read the title of the video. Now I am thoroughly impressed!

Code please ???

Wonderful!! Just wow ✨✨✨

Love the visualization

Dijkstra's algorithm looks like how a slime mold navigates toward food.

Can you make a tutorial of how make this?, this is incredible

is it faster to climb straight over a mountain or go around it? the length of the path may be longer, but the amount of time it takes to traverse is shorter i submit that the a* implementation found the shortest *temporal* route the expressways and bypasses it picked _should_ be faster timewise due to their higher speed limits and lower number of traffic lights

Is there any documentation or resource to learn how to create this node map to run a simulation based on our algorithm?

@Mohammed_Fahad_1

6 ай бұрын

Would be really helpful for us too : )

Looking at the video description, you can implement A* with greedy-best-first search since those are two different algorithms. So this is more of a Djikstra va Greedy-best-first search.

Great visu ! Do you have a Git where we can follow your work ?

would be cool to see how you made the visualisations

So it comes down to: "Are you more in a rush of finding a path or to actually go there?"

finnally I found it, thanks

Is it possible for Dijkstras algorithm to log all the paths to all the nodes it searched on the journey to its Destination? Then you store these for later retrieval?

Those algos might seem similar to unexperienced programmers, but they are diffirent things and serve diffirent purposes. A* is a pathfinding algorithm and Djkstra is a mapping algorithm. Therefore it processes much more data than A* given the same dataset. For example, in a game, use djkstra to map information on the game envirnoment for AI, and use A* for player controlled entities.

@blissful4992

5 ай бұрын

No. A* is an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.

I think you used a bad heuristic for A* . I was yelling “Manhattan Distance” at my screen, i bet that would work really well in NY example. Edit: Remembering A*, the heuristic works best if it (almost) always better than the real path. So euclidian distance at 60mph should work. Curious what you used?

@blissful4992

5 ай бұрын

This isn’t A*. Look at the description

can you make a tutorial how you do that, especially with blender python api

Excelent Job! Which tools have you used to make this?

@anthonymadorsky1551

6 ай бұрын

Thanks for the compliment! I have added some more details to the video description.

I don’t know if it’s really a proper pathfinding algorithm if it doesn’t find the shortest path.

@homeworkhopper4610

6 ай бұрын

Dijkstra's guarantees the shortest path, but only because it searches every single node at each depth before looking further. There are many graphs which cannot be practically searched this way in a reasonable amount of time. A* can handle some of these graphs in a reasonable amount of time, but in order to do so it may have to sacrifice the ability to always find the shortest path (A* can still find the shortest path if given a proper heuristic, but it was clearly not given a good heuristic here). Ultimately, there are many cases when we need an algorithm that can simply find any path at all rather than the shortest one, specifically. In this sense, A* is definitely still a pathfinding algorithm, even if it doesn't necessarily find the best path.

@NihongoWakannai

5 ай бұрын

​@@homeworkhopper4610 yeah, especially for a weighted graph then I don't believe there is any proper heuristic that wouldn't require costly pre-processing of the graph. For game AI, A* is super useful because I just need a "pretty good" path calculated very fast.

@blissful4992

5 ай бұрын

@@homeworkhopper4610 Uh no that's now how A* works. You are describing algorithm A not A*. A* is used to describe algorithm A with a admissible heuristic: one that will produce a optimal path every time. Aka heuristic

This is not the fastest route on either one, this is a simulation of a path of least resistance (A*) and the other is a simulation of first discovery (Dijkstra) both can connect the dots, neither are exactly accurate. A* is unable to represent the speed of an object since Evey line has its own speed. Every intersection is a dilemma, and the less decisions it has to make the faster it moves. Dijkstra is unable to connect obvious paths if the map appears broken until a path that connects the two is discovered. It then automatically assumes that this is the fastest path (first discovery) as seen in the last example. Even if there is a more efficient path.

Is it possible to merge the intentions of both algorithms to find a partially efficient path while also ensuring there’s a lesser time for the algorithm to calculate?

@thesimpilot2022

5 ай бұрын

I read through like 5 comments and I figured out they were people with an intellectual level 10 times higher that my standard 9th grade A scoring self right when I saw heuristic checking as a term

@Karak-_-

5 ай бұрын

In a way, yes. What they claim is "A*" is not really A* it's Greedy-Best-First Search. When make a path, Dijkstra makes decisions based on distance from start to the next step, while Greedy-Best-First Search makes decisions based on distance it (inaccuraty) guesses (that's the heuristic) there is between the next step. A true A* combines both aproaches and makes decision based on the sum of both.

That poorly-implemented A* reminds me of that ancient Intel joke: me: what's 27/14 pentium: 3 me: that's wrong pentium: maybe, but fast!

Coud you do tutorial on how to work with geo data?

Great stuff! :)

@anthonymadorsky1551

6 ай бұрын

Thank you so much for commenting! Your video from a few months ago on A* visualization was a huge inspiration to my group! I hope you have an excellent holiday season

@Creeperking-bw7wi

6 ай бұрын

Yeah it's pretty cool but this isn't even A*

Dijkstra: The evil empire is hunting for you. A*: The evil empire is hunting for you - and they have spies everywhere.

Dijkstra is like doing work meticulously. A* is like doing "ehh, whatever, close enough."

@m.sierra5258

2 ай бұрын

That's not true; A* also finds the best solution. It just has extra information to prevent it from walking in the wrong direction. As a sidenote: The algorithm shown in the video is not an A*, it seems to be a greedy heuristic path finding algorithm. A* is guaranteed to return the same result as Djikstra. Djikstra can actually be expressed as an A* with the "walk in the right direction" heuristic set to zero.

This is wild but the location you chose on the new york map is my house

Para saber realmente cual es mejor seria probandolo en la vida real los dos tipos de sistemas, teniendo en cuenta el trafico y las distintas velocidades de las vias ya que muchas veces el mas corto no es el mas rapido

A* is optimized dijkstra. If yout set the weight of the cost funtion to zero in A*, you basically only the path information(Dijkstra).

A* is so much faster that it can afford to find a number of more paths so it can then evaluate the shortest of those.. and still likely finish processing faster than Dijkstra.. so it would be faster and very likely to provide the shortest route every time..

Hello, Please can someone tell me how to do this, is there any github repo on this project, please let me know if anyone has resources on this ?

At 2:13 the A* should never have gone to the top left of the map. Something is wrong here.

Turns out one cannot simply use the Manhattan distance in Manhattan.

Either that A* is not properly implemented or they're using a Potato as heuristic.

Fun fact. A* breaks apart when you have more then 1 target. Because it turns into O(X) while the other one stays at O(1) no matter how many targets are left.

@arikontinen7688

5 ай бұрын

Fun fact. A* does not break with multiple goals if you know what you are doing. Just search in reverse. Make the original start the goal and all the original goals as open nodes and it trivially finds the closest goal in a single search. It also works just fine with multiple goals if you just make the heuristic be the euclidian distance to the nearest goal. It will take longer than the reverse search but it will still give you the shortest path with only a single search. The only thing that breaks A* is wormholes(nodes with a cost of zero in between them). For all other problems you might encounter while using A* there is a simple solution if you know what you are doing.

@Speiger

5 ай бұрын

@@arikontinen7688 It breaks apart because the computational cost becomes just that much worse, while Dijkstra's algorithm stays the same. Ofc you can try to optimize the way you aproach it, but A* stays always in the multiplier cost and sadly that's not avoidable :) Also you can optimize Dijkstra's algorithm to be a lot quicker. If your target is rather close and you know the distance you can simply stop nodes from scanning if their total travel distance exceeded the furthest target distance reached. And you can keep track if all targets were found :)

@arikontinen7688

5 ай бұрын

@@Speiger Yeah sorry to tell you this but you are just wrong. A* will always be the same or fewer operations than dijkstra no matter what you are doing. Does not matter if you have multiple targets or not. If you only need to find the best path to any one of the targets A* will be better. If you need a path that visits all the targets then use A* to find distances between each pair and after that solve for the traveling salesman problem. If you try to use dijkstra to find a path that visits all targets directly without first working out the distance between pairs etc it will scale O(X^X) and you will regret your decision to even attempt doing it that way. And if you are not trying to solve the traveling salesman problem you should never need to find a path to all the targets. Just the closest one. If your implementations show a different result then you implemented A* wrong or your graph is too small that the difference gets lost in the noise. Also dijkstra is not O(1). Both dijkstra and A* scale with the size of the graph. A* however scales a lot better. If someone claims there is a situation where dijkstra scales better than A* they do not know what they are talking about.

@Speiger

5 ай бұрын

​@@arikontinen7688 You misunderstood the problem. Lets take for example Oxygen not included (ONI) Which is a game where a dupe (character) can walk to a resource and pick it up. The problem is that there can be hundreds or thousands of resource objects laying around. When you use A* to calculate paths you either have to do each one one by one, which technically you could multithread. Or you could use dijkstra to simply scan the entire map and have paths to every single one in 1 rush. The traveling merchants problem has nothing to do with dijkstra's strengths, its an entirely different problem because it assumes 1 starting point and you want to visit all targets in the fastest order, while dijkstra's strength is: I want to find X and i have 500 possible connections, which one is the closest or which are the paths to all of them. Edit: Knowing all paths can be also useful because you can simply cache them and update them as you walk so you don't have to path again. A* will simply break by the amount of overhead due to duplicated work since it can't really keep existing work and unless all paths have 0 overlap you are a lot faster with dijkstra then with A* To go back to ONI, you will have a ton of duplicated pathing which means dijkstra's algorithm will simply outperform A* by miles. If you can't see that in this scenario which is really common in building games then i am sorry you have no idea you are talking about. Now to make concessions: dijkstra isn't the perfect algorithm that beats everything. It is really good if you have a ton of targets or don't know where your targets are like you can not calculate a "distance" at all. But the moment either of these are not a factor it breaks apart and is really slow. A* on the other hand is really good if you have information about distance and you have single targets. Which a TON of cases have. Then A* is really hard to beat. But A* isn't as perfect as people make it out to be. Know the cons and strengths of your algorithms.

@arikontinen7688

4 ай бұрын

@@Speiger No. You misunderstood the solution. A* does not need to do any duplicated work. In your ONI example with A* you would put all the resources as open nodes(starting postitions) and the dupe as the goal. Initiate the search and it will find the closest resource to the dupe faster than dijkstra with a single search no duplicate work needed. Or if you want to search from the dupe to the resources, your heuristics is the distance to the resource closest to the node but that is the slower approach as your heuristic function becomes quite slow. You do not do them one by one. You add them all at the same time and the algorithm searches from the best candidates first. If you actually understood how these algorithms work you would have known that. Dijkstra is just A* with a heuristic of 0. Which means that no matter what as long as the heuristic is admissible(the guessed distance to the goal is always smaller or equal to the real distance) then at the worst case scenario A* matches dijkstra and on average it always beats it. It only breaks if the graph contains nodes with a cost of 0 or lower between them because that forces the guess to always be zero which effectively forces it to perform the same as dijkstra. This is a fact and no matter how you try to define the problem it will not change. If your heuristic is admissible A* will never search a node that dijkstra does not search. If the heuristic is admissible then there is no problem where A* would search more nodes than dijkstra. It is simply impossible. Any time you think you have found a case where dijkstra is better than A* you have just implemented A* wrong.

Why don't the source and target actually line up with the map

why does it flash bang me when it finds the path?

Cool, but A* and Dijkstra should return the same shortest path

@myithspa25

5 ай бұрын

Why is that?

@Zeos-pk3wh

5 ай бұрын

@@myithspa25because if implemented correctly, both algortihms should return the single shortest path, of which there is only one

@blissful4992

5 ай бұрын

@@Zeos-pk3wh Not necessarily only ONE, but only one length yes

@mx.olydian2111

5 ай бұрын

Nope, Dijkstra searches all directions evenly whereas A* is weighted by the "as the crow flies" distance to the objective Dijkstra always find the shortest path, A* compromises that goal to prioritise minimising search time, they behave totally differently

your description says you used “greedy best first logic” - that is not A* which is why you don’t get the optimal solution

What was the heuristic function used in this implementation?

@blissful4992

5 ай бұрын

They didnt use A*. They used Greedy-Best-First Search.

Tutorial de como usar blender please!

I just got flashbanged a few times

Dijkstra: wait 19 seconds for a path, spend 35 minutes driving to destination. A*: wait 3 seconds for path, spend 1 hour 5 minutes driving to destination. I'd prefer Dijkstra, I think.

WHY DID YOU FLASHBANG MEEEEEEEEEE

Does A* have to flashbang us?

Ok so A* finds a path fastest and Dijkstra finds the fastest path? The comparison seems a little weird.

@user-dg9qf7me8y

6 ай бұрын

Why is the comparison weird? They're both pathfinding algorithms. They simply serve different purposes.

@redbeardrichard

6 ай бұрын

Oh i thought this was a speed comparison. My bad.

@bogdansavianu6658

6 ай бұрын

A* in this case was implemented incorrectly. It always finds the shortest path if implemented correctly.

@redbeardrichard

6 ай бұрын

Ok, so it should find the shortest path? I don’t really know much about this, but I’m very interested. I once implemented Djikstra as a path finding algorithm in a simple game. That’s why I was surprised to find something so much faster. But then I saw that It took a much longer route.

@jefferywu2624

6 ай бұрын

@@redbeardrichardYes, A* should also find the shortest path if implemented correctly.

Fix the title this is not A* it's just A

Oh, so that's why gps in GTA games are always wrong.

@Creeperking-bw7wi

6 ай бұрын

They implemented A* incorrectly. A* always finds the shortest path they just made a mistake

😮

Imagine an AI enhanced A* algorithm that has been trained on billions of these examples.

a star assumes to always know the absolute distance

@blissful4992

5 ай бұрын

no, thats a heuristic, not the algorithm itself

@0MVR_0

5 ай бұрын

@blissful4992 actually that is a part of the algorithm. A heuristic can have a portion of total knowledge, rather than exclusively local vantage. A star is only more efficient because the bird's eye distance of each node to the destination is known, which is a form of optimal selection filtering. edit: literally called a star because "true north" is calculable

@blissful4992

5 ай бұрын

@@0MVR_0 False. Multiple heuristics exist that aren’t purely based on distance. Different distance heuristics exist aswell, like Euclidean and Manhattan.

@0MVR_0

5 ай бұрын

@@blissful4992 pedantic and irrelevant. a star utilizes absolute meter which is the critical factor for its optimality

Singapore research !

A* is basically Dijkstra with heuristics. If you don't have the same results it means you did a poor job implementing dijkstra base

@minutenreis

5 ай бұрын

after reading their comments they probably fucked up A* instead (and implemented some greedy first algorithm)

@mx.olydian2111

5 ай бұрын

Yeah A* without the heuristic IS Dijkstra, which means that the differences in the output are going to be consequences of your heuristic

A* is not implemented correctly. Why bother looking for a first arbitrary path solution, we want the shortest.

very beautiful project , i want to make my own,please guide me, i am currently learning sorting algos in python

You could have shortened this video by probably at least a minute by not pausing so long dude.

@blissful4992

5 ай бұрын

... and implementing A* correctly

A* is fast, but it’s weakness is obvious: moving backwards as part of the solution

Of course it starts in Rome. All roads lead to Rome.

what? you are unable to at least read some english text and tell us what tf is that a* algorithm?