数模论坛

 找回密码
 注-册-帐-号
搜索
热搜: 活动 交友 discuz
查看: 3337|回复: 1

[求助]谁能提供求解最小控制集的算法原程序?

[复制链接]
发表于 2003-8-17 05:13:51 | 显示全部楼层 |阅读模式

    图论中的求最小控制集虽然有通过邻接矩阵来求的方法,但这只适合于阶数较底的图,当阶数很大时(比如n=99),实际手工操作就很难了。在下急需求最小控制集的现成算法程序,急切盼望各路建模朋友能尽快提供(只有几天时间了啊!!)?在下先在此感激不尽!!!!(或者在那里可以找到啊)
  本人e-mail:phychem.student@sina.com
发表于 2003-8-18 08:40:43 | 显示全部楼层
给你思路吧。
1、首先题目归结为图论问题,为0说明无连接,为1说明有连接,设每个连接距离都
是1,然后用Floyd算法可以得到每两点之间的距离,得到的将是一个N*N(设N=1000)的距
离矩阵,如果矩阵值为有限数,说明两点之间是可以通过其他节点转接起来的,也
就是说这两点有广义连接,如果值为无穷,这就是没有可能连接起来。
2、然后就是去分析一下这个矩阵,遍历每一个节点,找该行中有广义连接的节点归
为一类,也就是将节点进行分类。
all mark=0; (i=0,1,...999)
class数组为有广义连接的节点集合。
iCount=0;
for(i=0;i<1000;i++)
{
if(mark) continue;
找第i行不为无穷大的点集{x1,x2...xn} (这里n不是题中的N,应该视有广义连接点
的数目而定,点集还有可能是空集)
mark[x1]=1;mark[x2]=1;...mark[xn]=1;mark=1;
class[iCount++]={x1,x2...xn}

}
这段伪码后,图中就可以被分为好几个类,每个类内部都是有广义连接、类与类之间
却没有任何连接。

最后这些控制集就是这些类了。
您需要登录后才可以回帖 登录 | 注-册-帐-号

本版积分规则

小黑屋|手机版|Archiver|数学建模网 ( 湘ICP备11011602号 )

GMT+8, 2024-3-29 01:21 , Processed in 0.052108 second(s), 18 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表