注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

千鸟

本blog所有日志均系原创 转载请注明出处

 
 
 

日志

 
 

人工智能(java)--子图判断 1  

2007-04-25 21:48:15|  分类: Arithmetic |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

人工智能(java)--子图判断 1 - souljava - 千鸟  写个牛烘烘的名字先:人工智能之子图判断.

    一边写一边发. 个把月前,和项目的客户中科院药物研究所的熊sir说到,化学分析工具jchem时,他考我的题目,当时蒙了.此后一直耿耿于怀,
要解决的问题是这样的, 有两个分子,要判断一个分子能否化和成另一个. 只把它考虑成可能的数学结构组合: 把分子看成由节点组成的图.
分成下面几种情况,步步扩展解决问题.

1. 每个节点最多两个两个邻居,每个节点不能有相同邻居.
2. 每个节点有多个邻居节点,每个节点不能有相同邻居
3. 有几个环,节点可以有相同邻居
4. 加入分子的空间位子的考虑,判断子图.(这个才是分子结构种的标准样式)
  
   大图是a,小图b.
对于上述情况1.最简单,没写代码,算法描述如下:

遍历b,存入一个数组.
然后遍历图a.若当前节点和b游标指示的节点符合, 游标+1,当到b的游标加到尽头,返回true. B能组成a. 若不符合, b的游标指到0,然后从a的下一个节点开始遍历. 遍历过的节点填上true标记.当a的邻居都为true时, 返回false,.b不能组成a.

对于上述情况2. 描述如下:
用递归的方式判断,每个节点的邻居.  对访问过b图的节点 设置标记visited标记true

下面的代码中,图的输入方法,比图算法的输入的时候有的了很大的进步了.像下面代码主函数中的写好字符串类型的表示方法.调用public LinkedList creatGraph(String path)就可以生成逻辑图了.

对于上述情况3,4,还在研究中,看看这个blog的看客,能不能比我先解决.

下面是情况2的代码,

左边是小图,b图.右边是大图,a图

人工智能(java)--子图判断 1 - souljava - 千鸟人工智能(java)--子图判断 1 - souljava - 千鸟
 



/*
 * ZiTu.java
 * author: liuke
 * email: soulnew@gmail.com
 * Created on April 21, 2007, 10:34 PM
 */

package com.soulnew.ZiTu;
import java.util.*;
import com.soulnew.ZiTu.*;

public class NewZiTu{
   
    public NewZiTu(){
       
    }
    public NewZiTu(String edges){
       
    }
    public static void main(String args[]){
       
        NewZiTu zitu=new NewZiTu();
        //  String path="a-b,b-d,b-c";
        String graph_a="a-b,b-c,c-d,d-e,d-b,a-t,c-e,d-e";
        String graph_b="a-b,b-c,c-d,d-e";
     
        LinkedList la= zitu.creatGraph(graph_a);
        LinkedList lb= zitu.creatGraph(graph_b);
//        zitu.visitLinkedList(la);
//        System.out.print("\n");       
//        zitu.visitLinkedList(lb);
       
       System.out.print(zitu.doJudge2(la, lb));
       
    }
    /*
     访问逻辑节点
     */
    public void visitLinkedList(LinkedList l){
       
        for(int i=0;i<l.size();i++){
            System.out.print(((Node)l.get(i)).toString());
        }       
       
    }
    /*
      遍历图中的每个节点和它的邻居节点
     */
    public  void visitGraph(LinkedList l){
        for(int i=0;i<l.size();i++){
           
            Node temp=(Node)l.get(i);
            System.out.print("\n"+temp.toString()+":----");
            for(int ii=0;ii<temp.neighbors.size();ii++){
                System.out.print(((Node)temp.neighbors.get(ii)).toString());
            }
        }
    }
   
   
    /*
     在a图中找到和b节点相同的节点,以链表返回
    
     */
    public LinkedList getFitNode(LinkedList a,Node b){
       
        LinkedList Fit=new LinkedList();
     /*   while(!a.isEmpty()){
            Node temp=(Node)a.getFirst();
            a.removeFirst();
            if(temp.name.equals(b.name))
                Fit.add(temp);
        }*/
        for(int i=0;i<a.size();i++){
            Node temp=(Node)a.get(i);
            if(temp.name.equals(b.name))
                Fit.add(temp);
        }
        return Fit;
    }
   /*
    是doJudge(LinkedList a,LinkedList b)的修正版本
    * 所以叫doJudge2
    */
    public boolean doJudge2(LinkedList a,LinkedList b){
        if(!HashJudge(a,b)){
            return false;
        }
        LinkedList lktemp=getFitNode(a,(Node)b.getFirst()); //选取a中可能的起点
        System.out.print(lktemp.size());
//        System.out.print("\n");
//        visitLinkedList(b);
//        System.out.print("\n");
//        visitLinkedList(a);
        for(int i=0;i<lktemp.size();i++){
            Node na=(Node)lktemp.get(i);
            Node nb=(Node)b.get(i);
            if(compareNeighbors(na.neighbors,nb.neighbors)){
                return true;
            }
        }
        return false;
    }
    /*
     比较邻居
     */
    public boolean compareNeighbors(LinkedList na,LinkedList nb){
        if(!HashJudge(na,nb)){
            return false;
        }
        for(int i=0;i<nb.size();i++){
           
            Node Bnode=(Node)nb.get(i);
            if(Bnode.visited)
                continue;
            Node Anode= LinkedListgetAsName(na,Bnode.name);
            //   Anode.visited=true;
            Bnode.visited=true;
            if(!compareNeighbors(Anode.neighbors,Bnode.neighbors))
                return false;
        }
        return true;
    }
    /*
     获取指定名字的节点
     */
    public Node LinkedListgetAsName(LinkedList a,String name){
       
        Node n=null;
        for(int i=0;i<a.size();i++){
            if(((Node)a.get(i)).name.equals(name)){
                return (Node)a.get(i);
            }
        }
        return n;
    }
    /*
     用哈西表的方式判断,b表是否包含a表的元素
     */
    public boolean HashJudge(LinkedList a,LinkedList b){
        if(a.size()==0&&b.size()==0)
            return true;
        Hashtable compare =new Hashtable();
        for(int i=0;i<a.size();i++)
            compare.put(((Node)a.get(i)).name, i);
        int asize=compare.size();
        for(int ii=0;ii<b.size();ii++){
            compare.put(((Node)b.get(ii)).name, ii);
        }
        if(compare.size()>asize){
            return false;
        }
        return true;
       
    }
   
   
   
    /*
     * 创建根据输入的字符创建双向图.
     * 节点之间用"-"分割,输入的下一组与上一组以","分割. 如:"a-b,b-c"
     */
    public LinkedList creatGraph(String path){
        LinkedList lk=new LinkedList();
        Hashtable temphash=new Hashtable();
       
        for (StringTokenizer t = new StringTokenizer(path, ",") ; t.hasMoreTokens() ; ) {
            String str = t.nextToken();
            int i = str.indexOf('-');
            if (i > 0) {
               
                String qian=str.substring(0,i);  //获得前节点的name
                String hou=str.substring(i+1,str.length());  //获得后节点的name
               
                Node qiannode=(Node)temphash.get(qian);
                Node hounode=(Node)temphash.get(hou);
                if(qiannode==null){                 //判断有没有建立这个键
                    qiannode=new Node(qian);
                   
                }
                if(hounode==null){
                    hounode=new Node(hou);
                }
                qiannode.neighbors.add(hounode);   //分别添加邻居节点
                hounode.neighbors.add(qiannode);  //如果要修改成单向图,其中有个邻居就可以不加了
                temphash.put(qian,qiannode);      //增加了邻居,所以要覆盖原来的信息
                temphash.put(hou,hounode);
               
            }
        }
        Iterator i=temphash.values().iterator();
        lk=new LinkedList();
        for(;i.hasNext();){
            lk.add((Node)i.next());
           
        }
        return lk;
    }
}

class Node{
   
    String name;
    boolean visited=false; //未被访问
    Node parents;
    LinkedList neighbors=new LinkedList();
    public Node(String name){
        this.name=name;
    }
   
    public List getNeighbors(){
        return neighbors;
    }
    public String toString() {
        return name;
    }
}
 


 

  评论这张
 
阅读(642)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017