UNIT II

Searching Techniques

Introduction

We have outlined the different types of search strategies. In the earlier chapter we have

looked at different blind search strategies. Uninformed search methods lack problemspecific

knowledge. Such methods are prohibitively inefficient in many cases. Using

problem-specific knowledge can dramatically improve the search speed. In this chapter

we will study some informed search algorithms that use problem specific heuristics.

Review of different Search Strategies

1. Blind Search

a) Depth first search

b) Breadth first search

c) Iterative deepening search

d) Bidirectional search

2. Informed Search

Informed Search and Exploration

Graph Search Algorithm

We begin by outlining the general graph search algorithm below.

Graph search algorithm

Review of Uniform-Cost Search (UCS)

We will now review a variation of breadth first search we considered before, namely

Uniform cost search.

To review, in uniform cost search we enqueue nodes by path cost.

Let g(n) = cost of the path from the start node to the current node n.

Version 1 CSE IIT, Kharagpur

The algorithm sorts nodes by increasing value of g, and expands the lowest cost node of

the fringe.

Properties of Uniform Cost Search

• Complete

• Optimal/Admissible

• Exponential time and space complexity, O(bd)

The UCS algorithm uses the value of g(n) to select the order of node expansion. We will

now introduce informed search or heuristic search that uses problem specific heuristic

information. The heuristic will be used to select the order of node expansion.

Comparison With Requirements

•             Users can’t certify TPs, so CR5 and ER4 enforce this

•             Procedural, so model doesn’t directly cover it; but special process corresponds to using TP

•           No technical controls can prevent programmer from developing program on production system; usual control is to delete software tools

•             TP does the installation, trusted personnel do certification

   CR4 provides logging; ER3 authenticates trusted personnel doing installation; CR5, ER4 control installation procedure

•           New program UDI before certification, CDI (and TP) after

•             Log is CDI, so appropriate TP can provide managers, auditors access

•           Access to state handled similarly

Comparison to Biba

•      Biba

–   No notion of certification rules; trusted subjects ensure actions obey rules

–   Untrusted data examined before being made trusted

•      Clark-Wilson

–   Explicit requirements that actions must meet

–   Trusted entity must certify method to upgrade untrusted data (and not certify the data itself)

Key Points

•      Integrity policies deal with trust

–   As trust is hard to quantify, these policies are hard to evaluate completely

–   Look for assumptions and trusted users to find possible weak points in their implementation

•      Biba based on multilevel integrity

•      Clark-Wilson focuses on separation of duty and transactions