Navigation

    云、贵、川、渝IT人的圈子
    • Register
    • Login
    • Search
    • 主页
    • 问答
    • 话题
    • 热门
    • 圈子
    • 招聘
    • 活动
    • 项目

    生成与测试范式

    极客生涯
    1
    1
    21
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • luobengseng1
      luobengseng1 last edited by

      解决问题的直接方法是提出可能的解,然后检查每个提议,看是否有提议构成了解。人们称之为生成与测试范式。
      本文用n皇后问题阐释这种方法,n皇后问题涉及将n个皇后放在n×n的棋盘上,任何两个皇后都不互相攻击。也就是说,任何两个皇后都不应该占据相同的行、列或对角线。这些条件被称为问题的约束条件。
      在这个问题中,4个皇后需要放置在4×4棋盘上。总共有 或1820种方法来实现这个目标。这些提议的解中,有许多提议的解违反了问题的一个或多个约束条件。但是,如果为了不丢失解,一个可靠的生成器必须提出满足问题约束的、大小为4的任何子集。更一般地说,如果这个生成器提出了每个可能的解,那么这个生成器就是完备的。此外,如果提出的解被拒绝了,那么这个方案就不会再次被提议(事实上,每个成功的提议都只能提出一次)。换句话说,一个好的生成器应该是非冗余(noredundant)的。最后,回想一下,将4个皇后放置在一个4×4棋盘上有1820种方法。如果生成器没有提出明显不可行的解,那么这个生成器会相对有效。可以说,如果生成器拥有一些信息,允许其对提案做出一些限制,那么这个生成器就是知情的(informed)。
      求解4皇后问题的第一种方法是采用生成器,在最坏的情况下,这个生成器检查1820种将4个皇后放在4×4棋盘上的每一种方式。
      完全枚举法是一种搜索方法,它将查看所有位置,寻找问题的解。甚至在已经发现了这组位置不可能成功得到解的情况下,完全枚举法还是进一步得到了部分解。我们可以使用带有生成与测试范式的回溯。在推进过程中,允许测试模块查看一个可能的解。ae4efd88-e085-40e2-9146-c86b695544d0-image.png

      1 Reply Last reply Reply Quote 0
      • First post
        Last post
      8
      玻
      U
      A
      大
      A
      黑
      低
      天
      白
      快
      爱
      白
      美
      此
      荒
      为
      哭
      柳
      无
      真

      社群
      昆明网页设计交流吧
      友情链接
      • Funtask
      • Funtask 社区
      • SUWIS
      • 云南北大青鸟
      ©2019-2020 滇ICP备20006698号