Timeline for Finding cheapest route (turn costs 500, going straight costs 100)
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8 at 15:39 | answer | added | J_H | timeline score: 2 | |
| Apr 8 at 11:47 | answer | added | toolic | timeline score: 1 | |
| Apr 8 at 11:45 | history | edited | toolic | CC BY-SA 4.0 |
deleted 2 characters in body; edited tags
|
| Nov 18, 2020 at 16:54 | comment | added | sherloock | @RootTwo okay I will try that too. thanks!! I actually coded with only cost term. Not using huristic term. and If cost on getting dot A by a route is bigger than the past route to dot A, not append it to queue. So by doing this it reduces useless tries. I thought this would reduce more time than using huristic. Am i thinking wrong?? | |
| Nov 17, 2020 at 16:18 | comment | added | RootTwo | @sherloock, just use taxi-cab distance. The heuristic can be any estimate as long as it never overestimates the remaining cost. In this case, taxi-cab distance would have zero or one turn. If there are walls in the way, then the path would have more turns and a higher cost. So the taxi-cab distance would never be an overestimate. | |
| Nov 17, 2020 at 10:27 | comment | added | sherloock | @RootTwo how should Ibuild a huristic for this problem? It contains walls. | |
| Nov 16, 2020 at 21:52 | comment | added | RootTwo | Take look at A* search (A star search). | |
| Nov 12, 2020 at 3:39 | comment | added | sherloock | @AustinHastings I added photo | |
| Nov 12, 2020 at 3:37 | history | edited | sherloock | CC BY-SA 4.0 |
[Edit removed during grace period]; added 1 character in body
|
| Nov 12, 2020 at 3:00 | history | tweeted | twitter.com/StackCodeReview/status/1326721488825839617 | ||
| Nov 12, 2020 at 2:19 | comment | added | sherloock | @N74 umm I tried to do that... but I wonder how to do that. IF I USE QUEUE would that be shorter than mine???please explain more. Thank you | |
| Nov 12, 2020 at 2:10 | comment | added | sherloock | @AustinHastings there is photo below I think it might help you. for example 3×3, 0,0 0,1 0,2 1,2 2,2 it is shortest 4 straight roads and 1corner so 900$ | |
| Nov 11, 2020 at 22:50 | history | edited | Reinderien | CC BY-SA 4.0 |
deleted 44 characters in body; edited title
|
| Nov 11, 2020 at 21:16 | comment | added | N74 | Dynamic programming. Start from the end block and evaluate the minimum cost for each free block linked with it, then propagate until you arriverà to the starting block. | |
| Nov 11, 2020 at 19:26 | comment | added | aghast | Can you explain the math behind the score computation? If I divide the red/blue paths into corner vs. straight, the numbers don't add up. | |
| Nov 11, 2020 at 18:38 | history | asked | sherloock | CC BY-SA 4.0 |