一个回溯算法问题，请大家帮忙看看

[gongbao]

大概这个问题有些难度，欢迎感兴趣的前辈指教。我猜想是通过回溯（backtracking）解决，类似八王后问题。谢谢！明天我也会自己动手尝试解决的，现在是深夜，先睡觉了。
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

如图所示，目标：将图1中的黑白棋调换成图2中的位置。要求：只能向空格走一步，或者隔一个棋子跳向空格（图3）。
任务：写一个程序，寻找在15步之内完成调换的走法，并打印。例如：“3 -> 4, 5 -> 3, ......”

 

[dennistan2009]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[gongbao]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

你画一堆分割线是咩意思啊

 

[dennistan2009]

心如刀割。

 

[gongbao]

心如刀割。

为什么啊，我发个题，就伤害到你啦？

 

[woodenwang]

就用深度优先+回溯解即可，因为有15步的限制，所以不需要太过考虑时间复杂度，应该不难的，你试下看。

 

[asdfg12345678]

这个好像属于状态空间搜索问题，以前学过。。。

 

[dimples]

-

浏览附件487186
浏览附件487187

 

[千客万来]

-
浏览附件487183

浏览附件487185

你最近刻意远离热帖，是不是心里有什么鬼？

 

[dimples]

你最近刻意远离热帖，是不是心里有什么鬼？

什么热帖，是打架帖吧，我进去找抽？

 

[千客万来]

什么热帖，是打架帖吧，我进去找抽？

继续你的学术

 

[gongbao]

-

浏览附件487186
浏览附件487187

一网哥动作好快！

 

[dennistan2009]

我举手投降，没辙。
问一下一网哥，这个是什么代码编辑器？

 

[gongbao]

我举手投降，没辙。
问一下一网哥，这个是什么代码编辑器？

好像是visual studio || intelji IDEA

 

[asdfg12345678]

这个问题我有印象，需要用启发式搜索，构造一个评估函数，每走一步就用函数评估一下当前得分，要保证每走一步，函数的得分都是增加或者非减的。
这是人工智能AI中的一类问题。
不要用深度优先或者广度优先。

 

[gongbao]

可以写下代码吗？我们没有学过启发试搜索

这个问题我有印象，需要用启发式搜索，构造一个评估函数，每走一步就用函数评估一下当前得分，要保证每走一步，函数的得分都是增加或者非减的。
这是人工智能AI中的一类问题。
不要用深度优先或者广度优先。

 

[asdfg12345678]

找本AI的书看看
懂了算法，写代码很简单。我给你写了代码，你还是不理解，也白搭。

 

[dimples]

家园园友xiaoa说过一句话，talk is cheap, show me the code : )

 

[asdfg12345678]

就那个号称在大家拿培训3个月coding就年薪10万的？
这样的骗子有人信吗？
恐怕他连上面我说的什么意思都看不懂。3个月他也就会写个hello world。呵呵

 

[gongbao]

找本AI的书看看
懂了算法，写代码很简单。我给你写了代码，你还是不理解，也白搭。

安卓编程用了点tensorflow. 不过这题目的真的不是考察AI,我们还是立足经典算法的学习阶段