COMP4418代做、代写c/c++，Python程序

日期：2023-10-11 09:43

COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3

Requirements

• Due date: October 6, 2023 at 11:55PM. This is an individual assignment. This assignment is weighted 15% of the course grade.

• Each student submits three files: assignment1.pdf, spiders.lp, and spidershortlegs.lp.

The file assignment1.pdf should contain the answers to questions 1.1, 1.2, 1.3, 2.1, 2.2,

and 3.1, including any snippets of code necessary.

Spanning Spiders

Let G = (V, E) be a graph. A spanning tree T is a subgraph of G with the following

properties:

• T is a tree (i.e. it contains no cycles and is connected).

• T contains all of the vertices of G.

A spider S is a tree with at most one vertex in S whose degree is 3 or more. Such a vertex

is called the centre of the spider. If S consists of no vertices with degree 3 or more, then any

vertex can act as the centre of the spider. Finally, a leg of a spider is a path from the centre

to a vertex of degree 1.

To get a better understanding of the terminology, consider the following example graph.

Figure 1: An example graph.

A possible spider is highlighted. In fact, the highlighted spider is a spanning spider because

it is a spider and a spanning tree.

Figure 2: A spider that is also a spanning tree.

1 of 3

COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3

Given an input graph, our goal is to write an Answer Set Program to return a list of distinct

spanning spiders (i.e. each stable model of our program corresponds to a distinct spanning

spider). Not every graph has a spanning spider; if an input graph does not admit any

spanning spiders, the corresponding program should return unsatisfiable.

Input format. An input file contains predicate instances of vertex/1, indicating the

vertices of the graph and predicate instances of edge/2, indicating the edges of the graph.

The example graph above is modelled with the following predicates.

vertex(a).

vertex(b).

vertex(c).

vertex(d).

vertex(e).

vertex(x).

vertex(y).

vertex(z).

edge(a, d).

edge(a, x).

edge(b, d).

edge(b, y).

edge(c, d).

edge(c, z).

edge(d, e).

edge(e, x).

edge(x, z).

edge(y, z).

Output format. Your program should compute a model containing a predicate leg/2,

indicating which edges are included in the spanning spider. Each model should also contain

a predicate centre/1, indicating which vertex is the centre of the spider.

2 of 3

COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3

Part I: Understanding the Problem

[1.1] Consider the spanning spider from Figure 2. Indicate the centre vertex and the list of

edges that is included in the spanning spider.

[1.2] Provide ASP rules to define the centre/1 predicate and ensure that in any model,

exactly one vertex is selected as the centre.

[1.3] Provide a generator for the leg/2 predicate.

Part II: Refining the Models

Up until now, you should have a set of models that consists of exactly one vertex as the

centre of the spider and a set of leg edges. Our goal is to now remove some of these models

that can form a spanning spider.

[2.1] One property required of spanning spiders is that every vertex should be reachable

from the centre through leg edges. Introduce a derived predicate reachable/1 that

ranges over vertex names and is true when the corresponding vertex is reachable from

the centre through leg edges. Use this predicate to define a constraint that ensures

every vertex of the original graph is reachable from the centre through leg edges.

[2.2] The reachability of every vertex from the centre is a required property of spanning

spiders, but it is not sufficient and we need to ensure other constraints are satisfied.

Describe all the other constraints that need to be satisfied and write ASP rules to

enforce these constraints.

We are now ready to write an ASP program that returns the set of spanning spiders, given

an input graph.

Part III: Putting everything together

[3.1] Based on your answers to the above questions, write an ASP program spiders.lp

that takes an input graph and outputs all the distinct spanning spiders of the graph.

How many distinct spanning spiders does the graph in Figure 1 have?

[3.2] Write an ASP program spidershortlegs.lp that outputs a spanning spider with the

shortest longest leg.

3 of 3