Algorithm 版 (精华区)

发信人: ssos (存在与虚无·英雄无敌), 信区: Algorithm
标  题: [合集]讨论：8数码问题是否必然有解。
发信站: 哈工大紫丁香 (2002年01月24日08:43:46 星期四), 站内信件


────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月03日17:48:24 星期一 说道:

不然的话，如何简洁地判断。
引申：今年上海第一题。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月03日17:49:02 星期一 说道:

详细说一下

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月03日18:49:49 星期一 说道:

八数码问题：
有一个3*3的棋盘，在每个格子分别放入0--8。如下：
1 2 3
4 5 6
7 8 0
放入0的格子可以和其上下左右四个格子中的任意一个格子交换，
一个交换称为一步。
问：给出两个状态，是否能从状态一经过有限次交换后变成状态二。
今年上海第一题：
有一个正方形，划分为四个小正方形，每个小正方形又划分为四个
三角形，每个三角形填入0-9的数字（0-9未必都填，也可重复填，这
和八数码问题是不同的）。填入0的三角形可以和其相邻的三角形（有公共边）
交换数字。
┌───┬───┐
│╲5 ╱│╲4 ╱│
│4 ╳ 9│6 ╳ 4│
│╱1 ╲│╱5 ╲│
├───┼───┤
│╲6 ╱│╲0 ╱│
│4 ╳8 │3 ╳4 │
│╱5 ╲│╱4 ╲│
└───┴───┘
问：给定一个状态，是否能通过像八数码问题那样的方法交换数字，
使相邻矩形公共边两边的数字相等，如下：
┌───┬───┐
│╲0 ╱│╲6 ╱│
│3 ╳4 │4 ╳8 │
│╱4 ╲│╱5 ╲│
├───┼───┤
│╲4 ╱│╲5 ╱│
│6 ╳ 4│4 ╳9 │
│╱5 ╲│╱1 ╲│
└───┴───┘
原题请去acm.shu.edu.cn下载。

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日11:21:56 星期二 说道:

这个问题Darcy很有研究。他曾经告诉我的是，其倒序数分奇偶两种情况，
奇的之间可以互相转化，偶的之间可以互相转化。相互之间则不能。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日14:19:38 星期二 说道:

这个用一般的搜索不行么??

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日16:36:06 星期二 说道:

你说今年上海的那一题？

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日18:10:04 星期二 说道:

nod
复杂度不是很大的说

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日18:25:57 星期二 说道:

感觉题目的要求不是求路径，可能会设置很多搜不到的数据。
而且本题的目标状态不止一个，会给搜索造成很大麻烦。

────────────────────────────────────────
 Lerry (戒网·学习)                   于 2001年12月04日18:27:41 星期二 说道:

搜索没有问题，就是没有解的时候耗时太长，占用内存太多，有时会不够用

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日18:29:28 星期二 说道:

faint
原来是证明存在性,这个需要证明了....

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日18:32:19 星期二 说道:

临时想到的,大家补充
第一步,看是否和是奇数
第二步,看是否存在这样的4组匹配,使得两两一组他们的和相等
(这个复杂度不会很大的说)
第三步,论证一下在什么情况下,两个单元可以互换

────────────────────────────────────────