不是可以用图论解决吗？
先把你的房间转化为一个图，然后选一种满足你约束的遍历算法。
实现这个算法就OK了。
不好意思，具体的知识俺忘记了。可以找本教材或者google一下

"Zoom.Quiet" <zoomq at infopro.cn> wrote:
Hollo Wang:

哈哈哈！！
去：
http://www.robochina.org/index.php
看一下子，就知道你这个极类似于最傻的tank 设计，
仅仅是要 可以自动走遍所有房间是也乎！！

其实可以蠕虫，又瞎又聋的，仅仅靠摸索吃过幼年期，

本身是个简单的自动吸尘机器人，不用停，只要
前进->是房间->清扫否?->左转或是右转->是墙?->左转或是右转

就可以了!
然后,想法子,打印出路线就可以知道最简单逻辑是否可行!


/******** [2004-9-12]15:57:50 ; Wang wrote:

Wang Chao> 有一个人工智能相关Python小程序，偶明白是要的什么东西，但是在系统如何走路上想不出来好的算法，而且因为刚接触Python，很多语句也不会写。

Wang Chao> 希望大家帮忙看一下。 谢谢~~~~~~。详细情况是这样的


Wang Chao> 现在已经有environment.py和Agents.py两个文件（代码附最后）

Wang Chao> 他们用来模拟吸尘器系统来执行一个1*2房间的清扫工作，但是目前的代码里没有任何智能，所以他会随机选择他的三个行动之一（左转，右转，洗尘），而不是根据判断当前的情况来选择行动。

>>>> import environment
>>>> from Agents import *
>>>> v=environment.VacuumEnvironment()
>>>> r=RandomAgent(agent_actions)
>>>> v.add_agent(r)

>>>> v.run(10)
Wang Chao> Initial room config: {(1, 0): 'Dirty', (0, 0): 'Dirty'}
Wang Chao> Percept: ((1, 0), 'Dirty') Action: Left
Wang Chao> Percept: ((0, 0), 'Dirty') Action: Suck
Wang Chao> Percept: ((0, 0), 'Clean') Action: Suck
Wang Chao> Percept: ((0, 0), 'Clean') Action: Right
Wang Chao> Percept: ((1, 0), 'Dirty') Action: Left
Wang Chao> Percept: ((0, 0), 'Clean') Action: Right
Wang Chao> Percept: ((1, 0), 'Dirty') Action: Left
Wang Chao> Percept: ((0, 0), 'Clean') Action: Left
Wang Chao> Percept: ((0, 0), 'Clean') Action: Left
Wang Chao> Percept: ((0, 0), 'Clean') Action: Suck
Wang Chao> Final room config: {(1, 0): 'Dirty', (0, 0): 'Clean'}

Wang Chao> 这就是执行的结果，当然，房间的初始状态也是随机的，系统的动作也是随机的，所以每次执行都不一样。


Wang Chao> 现在要想通过扩展原始代码，将房间环境扩展为3*3大小{(0,0),(0,1),(0.2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}，房间初始状态依然是随机，并且吸尘器的初始位置也随机。要求首先保证所有的房间都会被清扫，其次尽量减少系统的行动次数。
Wang Chao> 因为房间是3*3了，所以自然而然行动就变成了五个“上，下，左，右，洗尘”

Wang Chao> 要重写原来的def percept(self, agent):
Wang Chao> 来返回吸尘器当前看到的状态

Wang Chao> 重写原来的execute_action(self, agent, action):
Wang Chao> 通过吸尘器的行动，改变对应的环境状态。

Wang Chao> 刚接触Python，这两个东西还不太会写。不知道能否给出参考代码。

Wang Chao> 更困惑的是关于如何走路的算法。
Wang Chao> 假设房间是
Wang Chao> 00 01 02 
Wang Chao> 10 11 12
Wang Chao> 20 21 22
Wang Chao> 我可以规定到了第一个数字是0就不再执行up的动作，第二个数字是2就不再执行right的动作，类似这样的规则来限制系统的动作执行。但是系统不能因为能走就要走，还要有一个限制，如果已经走过了，是不应该再走的。但是假如我走到了21这个位置，该怎么走随随机选择一个么？假如随机后走到了20，然后发现10和21都走过了，那样岂不是就再也出不去了，22这个房间就再也不能被清扫了。
Wang Chao> 这本身就是矛盾的。
Wang Chao> 比较困惑，不知道有什么好的方法来解决这样的问题。

Wang Chao> 我能想到的是根据9种可能的初始房间号，写9个行走线路，来实现清扫，但这样显然就没有任何智能而言，假如房间扩大到10*10，这个代码就没法写了。

Wang Chao> 冥思苦想了两天了，始终不得其解，郁闷~~

Wang Chao> 附:environment.py

Wang Chao> import random

Wang Chao> class Environment:
Wang Chao> """Abstract class representing an
Wang Chao> Environment. 'Real' Environment classes
Wang Chao> inherit from this. Your Environment will
Wang Chao> typically need to implement:
Wang Chao> percept: Define the percept that an agent sees.
Wang Chao> execute_action: Define the effects of executing an action.
Wang Chao> Also update the agent.performance slot.
Wang Chao> The environment keeps a list of .objects
Wang Chao> and .agents (which is a subset
Wang Chao> of .objects). Each agent has a .performance slot, initialized to 0.
Wang Chao> Each object has a .location slot, even
Wang Chao> though some environments may not
Wang Chao> need this."""

Wang Chao> def __init__(self,):
Wang Chao> self.objects = []
Wang Chao> self.agents = []

Wang Chao> object_classes = [] ## List of classes
Wang Chao> that can go into environment

Wang Chao> def percept(self, agent):
Wang Chao> "Return the percept that the agent sees at
Wang Chao> this point. Override this."
Wang Chao> abstract()

Wang Chao> def execute_action(self, agent, action):
Wang Chao> "Change the world to reflect this action. Override this."
Wang Chao> abstract()

Wang Chao> def default_location(self, object):
Wang Chao> "Default location to place a new object with unspecified location."
Wang Chao> return None

Wang Chao> def exogenous_change(self):
Wang Chao> "If there is spontaneous change in the world, override this."
Wang Chao> pass

Wang Chao> def is_done(self):
Wang Chao> "By default, we're done when we can't find a live agent."
Wang Chao> return False

Wang Chao> def step(self):
Wang Chao> """Run the environment for one time step. If the
Wang Chao> actions and exogenous changes are independent, this method will
Wang Chao> do. If there are interactions between them, you'll need to
Wang Chao> override this method."""
Wang Chao> if not self.is_done():
Wang Chao> actions = [agent.program(self.percept(agent))
Wang Chao> for agent in self.agents]
Wang Chao> for (agent, action) in
Wang Chao> zip(self.agents, actions):
Wang Chao> self.execute_action(agent, action)
Wang Chao> self.exogenous_change()

Wang Chao> def run(self, steps=1000):
Wang Chao> """Run the Environment for given number of time steps."""
Wang Chao> self.printInitialState()
Wang Chao> for step in range(steps):
Wang Chao> if self.is_done():
Wang Chao> self.printFinalState()
Wang Chao> return
Wang Chao> self.step()
Wang Chao> self.printFinalState()

Wang Chao> def printInitialState(self) :
Wang Chao> """ SHow the initial problem state """
Wang Chao> pass

Wang Chao> def printFinalState(self) :
Wang Chao> """ SHow the final problem state """
Wang Chao> pass

Wang Chao> def add_object(self, object, location=None):
Wang Chao> """Add an object to the environment, setting its location. Also keep
Wang Chao> track of objects that are agents. Shouldn't
Wang Chao> need to override this."""
Wang Chao> object.location = location or
Wang Chao> self.default_location(object)
Wang Chao> self.objects.append(object)
Wang Chao> if isinstance(object, Agent):
Wang Chao> object.performance = 0
Wang Chao> self.agents.append(object)
Wang Chao> return self

Wang Chao> def add_agent(self, ag, location=None) :
Wang Chao> """Add an agent to the environment"""
Wang Chao> ag.location = location or self.default_location(ag)
Wang Chao> ag.performance = 0
Wang Chao> self.agents.append(ag)
Wang Chao> return self



Wang Chao> class VacuumEnvironment (Environment) :
Wang Chao> def __init__(self):
Wang Chao> Environment.__init__(self)
Wang Chao> self.status =
Wang Chao> {(0,0):random.choice(['Clean', 'Dirty']),
Wang Chao> 
Wang Chao> (1,0):random.choice(['Clean', 'Dirty'])}
Wang Chao> def percept(self, agent):
Wang Chao> "Returns the agent's location, and the
Wang Chao> location status (Dirty/Clean)."
Wang Chao> return (agent.location,
Wang Chao> self.status[agent.location])

Wang Chao> def printInitialState(self) :
Wang Chao> """ Show the initial problem state """
Wang Chao> print "Initial room config: ", self.status

Wang Chao> def printFinalState(self) :
Wang Chao> """ Show the final problem state """
Wang Chao> print "Final room config: ", self.status




Wang Chao> def execute_action(self, agent, action):
Wang Chao> """Change agent's location and/or
Wang Chao> location's status; track performance.
Wang Chao> Score 10 for each dirt cleaned; -1 for each move."""
Wang Chao> if action == 'Right':
Wang Chao> agent.location = (1,0)
Wang Chao> agent.performance -= 1
Wang Chao> elif action == 'Left':
Wang Chao> agent.location = (0,0)
Wang Chao> agent.performance -= 1
Wang Chao> elif action == 'Suck':
Wang Chao> if self.status[agent.location] == 'Dirty':
Wang Chao> agent.performance += 10
Wang Chao> self.status[agent.location] = 'Clean'

Wang Chao> def default_location(self, object):
Wang Chao> "Agents start in either location at random."
Wang Chao> return random.choice([(0,0), (1,0)])






Wang Chao> 附:Agents.py



Wang Chao> import random

Wang Chao> ### global variable holding all possible agent actions
Wang Chao> agent_actions = ['Left', 'Right', 'Suck']


Wang Chao> class Agent :
Wang Chao> """An Agent is a subclass of Object with one required slot,
Wang Chao> .program, which should hold a function that takes one argument, the
Wang Chao> percept, and returns an action. (What
Wang Chao> counts as a percept or action
Wang Chao> will depend on the specific environment in
Wang Chao> which the agent exists.) 
Wang Chao> Note that 'program' is a slot, not a
Wang Chao> method. If it were a method,
Wang Chao> then the program could 'cheat' and look at aspects of the agent.
Wang Chao> It's not supposed to do that: the program can only look at the
Wang Chao> percepts. An agent program that needs a
Wang Chao> model of the world (and of
Wang Chao> the agent itself) will have to build and maintain its own model.
Wang Chao> There is an optional slots, .performance,
Wang Chao> which is a number giving
Wang Chao> the performance measure of the agent in its environment."""

Wang Chao> def __init__(self):
Wang Chao> self.alive = True

Wang Chao> def program(percept):
Wang Chao> return raw_input('Percept=%s; action? ' % percept)


Wang Chao> ### In the 2 room environment, there are three
Wang Chao> actions: Left, Right and Suck

Wang Chao> class RandomAgent(Agent):
Wang Chao> "An agent that chooses an action at random, ignoring all percepts."
Wang Chao> def __init__(self, actions):
Wang Chao> self.actions = actions

Wang Chao> def program(self, percept) :
Wang Chao> action = random.choice(self.actions)
Wang Chao> print "Percept: %s Action: %s" % (percept, action)
Wang Chao> return action



********************************************/

-- 
Free as in Freedom

Zoom.Quiet 

#=========================================#
]Time is unimportant, only life important![
#=========================================#

sender is the Bat!3.0

_______________________________________________
python-chinese list
python-chinese at lists.python.cn
http://python.cn/mailman/listinfo/python-chinese





---------------------------------
Do You Yahoo!?
150万曲MP3疯狂搜，带您闯入音乐殿堂
美女明星应有尽有，搜遍美图、艳图和酷图
1G就是1000兆，雅虎电邮自助扩容！
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20040912/569099f6/attachment.html