-1
$\begingroup$

Is there any pathfinding trivial problems like the TSP?
I know that is possible to solve TSP using A*, Best-first and using spanning tree and other things as heuristic but, is there any problem well know by the AI community?

$\endgroup$
3
  • 1
    $\begingroup$ I don't understand your question. TSP is NP-complete: that's pretty much the opposite of being trivial. $\endgroup$ May 2, 2016 at 21:23
  • $\begingroup$ well, my point was. TSP is a popular problem, i would like to know another pathfinding problem that is as popular as tsp. $\endgroup$
    – PlayMa256
    May 2, 2016 at 22:18
  • $\begingroup$ Maybe look into some generalizations of TSP (you'll find examples from Wikipedia). $\endgroup$
    – Juho
    May 3, 2016 at 18:50

1 Answer 1

1
$\begingroup$

A different kind of pathfinding problem could be the solving of a sliding puzzle. Which can be implemented using a*. You can pass in a board configuration like:

ed_o
nmac
jibf
hglk

and find a path to an inputted solution:

abcd
efgh
ijkl
mno_

An admissible heuristic for this could be city-block distance.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.