我试图理解维基百科 ( http://en.wikipedia.org/wiki/Depth-first_search )上的规范 DFS 伪代码——特别是使用堆栈的非递归实现。
在 BFS 中，您在将一个节点推送到队列之前检查它是否已经被探索过，这保证了没有节点会被多次推送到队列中。但是在 DFS 中，您只在将节点从堆栈中弹出时检查它是否已经被探索。这似乎是故意的，正如维基百科页面所说：“[DFS] 延迟检查是否已发现顶点，直到顶点从堆栈中弹出，而不是在推送顶点之前进行此检查。”
但似乎这种延迟可能会导致节点不止一次被推入堆栈。例如，考虑图中节点 1 指向节点 2，节点指向节点 3，节点 4，依此类推，直到节点 100。这些节点中的每一个都指向节点 0。
考虑将 Wikipedia DFS 算法应用于此图，以节点 1 作为起始状态。首先，节点 0 将被压入堆栈。然后将推送节点 2。接下来，节点 2 将从堆栈中弹出，由于它尚未被探索，它的子节点将被推入堆栈，（不检查它们是否已经被添加到堆栈中！）。节点 2 的子节点是节点 0 和节点 3。接下来，节点 3 将被扩展，将节点 0 和节点 4 压入堆栈。这将一直持续到堆栈被 100 次出现的节点 0 填充为止。
我的问题是：为什么 DFS 与 BFS 不同，它会延迟探索检查是否会产生这种冗余？
我读到了Tesauro的TD-Gammon计划,并希望将其用于tic tac toe,但几乎所有的信息对我来说都是高中生无法访问的,因为我不知道术语.
这里的第一个等式,http://www.stanford.edu/group/pdplab/pdphandbook/handbookch10.html#x26-1310009.2
给出了"一般监督学习范式".它表示等式左边的w sub t是时间步t的参数向量."时间步长"究竟是什么意思？在设计用于输出电路板状态值的tic tac toe神经网络的框架内,时间步长是指给定游戏中播放的片段数量吗？例如,由字符串"xoxoxoxox"表示的板将在时间步骤9处并且板"xoxoxoxo"将在时间步骤8处？或者时间步骤是指自培训开始以来经过的时间量？
由于w sub t是给定时间步长的权重向量,这是否意味着每个时间步都有自己的评估函数(神经网络)？因此,要仅通过一次移动来评估电路板状态,您必须输入不同的NN,而不是通过两次移动来馈送电路板状态？我想我在这里误解了一些东西,因为据我所知,Tesauro只使用一个NN来评估所有的董事会状态(尽管很难找到关于TD-Gammon的可靠信息).
为什么输出的梯度取决于w而不是w sub？
提前感谢您澄清这些想法.我将不胜感激任何关于我的项目的建议或对易读阅读材料的建议.
machine-learning reinforcement-learning tic-tac-toe temporal-difference
我一直在尝试使用多层感知器和反向传播来编写一个用于tic tac toe的AI.我的想法是训练神经网络成为电路板状态的准确评估函数,但问题是即使在分析了数千个游戏之后,网络也没有输出准确的评估.
我正在使用27个输入神经元; 3x3板上的每个方块与三个输入神经元相关联,这三个输入神经元接收0或1的值,具体取决于方块是否具有x,o或空白.这27个输入神经元向10个隐藏的神经元发送信号(我任意选择10个,但我也试过了5个和15个).
对于训练,我已经让程序通过使用当前评估函数对自己进行比赛来生成一系列游戏,以选择被认为是每一方的最佳移动.在生成游戏之后,NN通过将给定板状态的正确输出作为其后面的板状态的值(使用评估函数)来编译训练示例(其包括板状态和正确的输出).游戏序列.我认为这是Gerald Tesauro在编写TD-Gammon时所做的,但我可能误解了这篇文章.(注意:我在本文的底部放置了更新权重的具体机制).
我已经尝试了各种学习率的值,以及不同数量的隐藏神经元,但似乎没有任何效果.即使经过数小时的"学习",战略上也没有明显的改进,评估功能也不会接近准确.
我意识到有更简单的方法来编写tic tac toe,但是我想用多层感知器做这件事,这样我以后可以将它应用于连接4.这甚至可能吗？我开始认为对于具有合理数量的隐藏神经元的tic tac toe板没有可靠的评估功能.
我向你保证,我不是在寻找一些快速的代码来完成家庭作业.我已经有一段时间没有成功工作,只想知道我做错了什么.所有建议表示赞赏.
这是我用于NN的具体机制:
27个输入神经元中的每一个接收0或1,其通过可微分的S形函数1 /(1 + e ^( - x)).每个输入神经元i发送此输出(i.output),乘以一些权重(i.weights [h])到每个隐藏的神经元h.这些值的总和被隐藏神经元h(h.input)作为输入,并且该输入通过sigmoid以形成每个隐藏神经元(h.output)的输出.我将lastInput表示为所有隐藏神经元中(h.output*h.weight)的总和.然后,板的输出值是sigmoid(lastInput).
我将学习率表示为alpha,并将错误表示为正确的输出减去实际输出.另外,我让dSigmoid(x)等于x点处的sigmoid的导数.
每个隐藏神经元h的权重增加值:(alpha*err*dSigmoid(lastInput)*h.output)并且从给定输入神经元i到给定隐藏神经元h的信号的权重增加该值:(alpha*err*dSigmoid(lastInput)*h.weight*dSigmoid(h.input)*i.output).
我从这个关于反向传播的讲座中得到了这些公式:http://www.youtube.com/watch？v = UnWL2w7Fuo8 .