algorithm: A* search and IDA* search

August 8, 2017

The post discusses some search methods.

problem

  • Given: a graph, a source node, and a destination node
  • Objective: find a minimum cost path from source to destination.
  • greedy search

    • bfs style
    • cost function = h(x): estimated cost of path to destination

    A search

    • bfs style
    • cost function = f(x) = h(x) + g(x). g(x): cost of path from source

    A* search

    • bfs style
    • cost function = f(x) = h(x) + g(x)
    • h(x) is admissive, i.e., h(x) <= h*(x). It never overestimates the cost to the destination.
    • the solution is optimal

    IDDFS: iterative deepening dfs

    • dfs style
    • cost function = g(x): length of the path from source
    • the search has many iterations of dfs
    • in each iteration, the dfs stops while path length is above threshold
    • the stop threshold is increased by one in each iteration

    IDA*: iterative deepening dfs

    • dfs style
    • cost function = f(x) = h(x) + g(x)
    • h(x) is admissive, i.e., h(x) <= h*(x). It never overestimates the cost to the destination.
    • the stop threshold is increased by one in each iteration
    • the search has many iterations of dfs
    • in each iteration, the dfs stops while path length is above threshold
    • the stop threshold’s default value is h(source)
    • if destination is not found in last iteration, the stop threshold is updated as the minimum f(x) above threshold in last iteration
    • the solution is optimal

    conclusion
    IDA* search improves the space usage of A* search. This could improve performance since all operations are executed in stack directly which is already created by kernel(main thread) or pthread library(other threads). However, since stack size is fixed, if the problem size is large, than A* search might be the better option.

    Advertisements

    aws: awscli: s3 and s3api

    July 31, 2017

    The post discusses using AWS CLI to request S3 service.

    environment

    bash-3.2$ sw_vers
    ProductName:    Mac OS X
    ProductVersion: 10.11.6
    BuildVersion:   15G1510
    bash-3.2$ python --version
    Python 2.7.10
    bash-3.2$ aws --version
    aws-cli/1.11.127 Python/2.7.10 Darwin/15.6.0 botocore/1.5.90
    

    aws configure
    AWS’s IAM(Identity and Access Management) service manages user, group and permissions. Each user granted AWS CLI permission is assigned a access key id and secret access key. aws configure can setup access key id, secret access key, and etc. In my case, the user is granted AmazonS3FullAccess permission.

    bash-3.2$ aws configure
    AWS Access Key ID [None]: $(access_key_id)
    AWS Secret Access Key [None]: $(secrect_access_key)
    Default region name [None]: 
    Default output format [None]: 
    

    s3 and s3api

    • aws s3 command provides high level s3 commands
    • aws s3api command provides low level s3 commands

    list all buckets
    Each data in S3 is in a bucket. The name of each bucket is globally unique for all users and regions.

    bash-3.2$ aws s3 ls 
    2017-01-18 14:24:52 bucket_name_01
    2017-07-31 13:53:14 bucket_name_02
    bash-3.2$ aws s3api list-buckets
    {
        "Owner": {
            "DisplayName": $(DisplayName), 
            "ID": $(ID)
        }, 
        "Buckets": [
            {
                "CreationDate": "2017-01-18T06:24:52.000Z", 
                "Name": "bucket_name_01"
            }, 
            {
                "CreationDate": "2017-07-31T05:53:14.000Z", 
                "Name": "bucket_name_02"
            }
        ]
    }
    

    list all objects in a bucket

    bash-3.2$ aws s3api list-objects --bucket bucket_name_01
    {
        "Contents": [
            {
                "LastModified": "2017-07-30T20:46:02.000Z", 
                "ETag": "\"af8a4df66bd9ef2433b3f29e07fbbac4\"", 
                "StorageClass": "STANDARD", 
                "Key": "hello.txt", 
                "Owner": {
                    "DisplayName": $(DisplayName), 
                    "ID": $(ID)
                }, 
                "Size": 12
            }
        ]
    }
    

    conclusion
    The post discusses using aws s3 and aws s3api to send requests to AWS s3 service.

    aws: command line interface

    July 31, 2017

    The post discusses AWS command line interface.

    environment

    bash-3.2$ sw_vers
    ProductName:    Mac OS X
    ProductVersion: 10.11.6
    BuildVersion:   15G1510
    bash-3.2$ python --version
    Python 2.7.10
    bash-3.2$ pip --version
    pip 9.0.1 from /Library/Python/2.7/site-packages/pip-9.0.1-py2.7.egg (python 2.7)
    

    api and aws
    The AWS service behaviours is controlled by API. Here shows using AWS CLI to control AWS service.

    install aws cli
    Use pip, python package manager, to install awscli package

    bash-3.2$ sudo pip install --upgrade awscli --ignore-installed six
    The directory '/Users/chengyihe/Library/Caches/pip/http' or its parent directory is not owned by the current user and the cache has been disabled. Please check the permissions and owner of that directory. If executing pip with sudo, you may want sudo's -H flag.
    The directory '/Users/chengyihe/Library/Caches/pip' or its parent directory is not owned by the current user and caching wheels has been disabled. check the permissions and owner of that directory. If executing pip with sudo, you may want sudo's -H flag.
    Collecting awscli
      Downloading awscli-1.11.127-py2.py3-none-any.whl (1.2MB)
        100% |████████████████████████████████| 1.2MB 746kB/s 
    Collecting six
      Downloading six-1.10.0-py2.py3-none-any.whl
    Collecting docutils>=0.10 (from awscli)
      Downloading docutils-0.13.1-py2-none-any.whl (537kB)
        100% |████████████████████████████████| 542kB 818kB/s 
    Collecting botocore==1.5.90 (from awscli)
      Downloading botocore-1.5.90-py2.py3-none-any.whl (3.6MB)
        100% |████████████████████████████████| 3.6MB 325kB/s 
    Collecting s3transfer<0.2.0,>=0.1.9 (from awscli)
      Downloading s3transfer-0.1.10-py2.py3-none-any.whl (54kB)
        100% |████████████████████████████████| 61kB 1.4MB/s 
    Collecting colorama<=0.3.7,>=0.2.5 (from awscli)
      Downloading colorama-0.3.7-py2.py3-none-any.whl
    Collecting PyYAML<=3.12,>=3.10 (from awscli)
      Downloading PyYAML-3.12.tar.gz (253kB)
        100% |████████████████████████████████| 256kB 1.4MB/s 
    Collecting rsa<=3.5.0,>=3.1.2 (from awscli)
      Downloading rsa-3.4.2-py2.py3-none-any.whl (46kB)
        100% |████████████████████████████████| 51kB 593kB/s 
    Collecting python-dateutil<3.0.0,>=2.1 (from botocore==1.5.90->awscli)
      Downloading python_dateutil-2.6.1-py2.py3-none-any.whl (194kB)
        100% |████████████████████████████████| 194kB 877kB/s 
    Collecting jmespath<1.0.0,>=0.7.1 (from botocore==1.5.90->awscli)
      Downloading jmespath-0.9.3-py2.py3-none-any.whl
    Collecting futures<4.0.0,>=2.2.0; python_version == "2.6" or python_version == "2.7" (from s3transfer<0.2.0,>=0.1.9->awscli)
      Downloading futures-3.1.1-py2-none-any.whl
    Collecting pyasn1>=0.1.3 (from rsa<=3.5.0,>=3.1.2->awscli)
      Downloading pyasn1-0.3.1-py2.py3-none-any.whl (61kB)
        100% |████████████████████████████████| 71kB 925kB/s 
    Installing collected packages: docutils, six, python-dateutil, jmespath, botocore, futures, s3transfer, colorama, PyYAML, pyasn1, rsa, awscli
      Running setup.py install for PyYAML ... done
    Successfully installed PyYAML-3.12 awscli-1.11.127 botocore-1.5.90 colorama-0.3.7 docutils-0.13.1 futures-3.1.1 jmespath-0.9.3 pyasn1-0.3.1 python-dateutil-2.6.1 rsa-3.4.2 s3transfer-0.1.10 six-1.10.0
    bash-3.2$ aws --version
    aws-cli/1.11.127 Python/2.7.10 Darwin/15.6.0 botocore/1.5.90
    

    aws usage
    The aws command can send client api all AWS service. For example EC2 and S3.

    bash-3.2$ aws
    usage: aws [options] <command> <subcommand> [<subcommand> ...] [parameters]
    To see help text, you can run:
    
      aws help
      aws <command> help
      aws <command> <subcommand> help
    aws: error: too few arguments
    

    show aws s3 document

    bash-3.2$ aws s3 help
    

    show aws ec2 document

    bash-3.2$ aws ec2 help
    

    conclusion
    The post discusses how to install AWS CLI, and shows its usage.

    reference
    AWS Command Line Interface
    Universal Command Line Environment for AWS.

    python: pip

    July 31, 2017

    The post discusses pip, package manager of python.

    environment

    bash-3.2$ sw_vers
    ProductName:    Mac OS X
    ProductVersion: 10.11.6
    BuildVersion:   15G1510
    bash-3.2$ python --version
    Python 2.7.10
    

    install pip
    Use easy_install to install pip.

    bash-3.2$ sudo easy_install pip
    Password:
    Searching for pip
    Reading https://pypi.python.org/simple/pip/
    Best match: pip 9.0.1
    Downloading https://pypi.python.org/packages/11/b6/abcb525026a4be042b486df43905d6893fb04f05aac21c32c638e939e447/pip-9.0.1.tar.gz#md5=35f01da33009719497f01a4ba69d63c9
    Processing pip-9.0.1.tar.gz
    Writing /tmp/easy_install-vuf8Jk/pip-9.0.1/setup.cfg
    Running pip-9.0.1/setup.py -q bdist_egg --dist-dir /tmp/easy_install-vuf8Jk/pip-9.0.1/egg-dist-tmp-mPnzBX
    /System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/distutils/dist.py:267: UserWarning: Unknown distribution option: 'python_requires'
      warnings.warn(msg)
    warning: no previously-included files found matching '.coveragerc'
    warning: no previously-included files found matching '.mailmap'
    warning: no previously-included files found matching '.travis.yml'
    warning: no previously-included files found matching '.landscape.yml'
    warning: no previously-included files found matching 'pip/_vendor/Makefile'
    warning: no previously-included files found matching 'tox.ini'
    warning: no previously-included files found matching 'dev-requirements.txt'
    warning: no previously-included files found matching 'appveyor.yml'
    no previously-included directories found matching '.github'
    no previously-included directories found matching '.travis'
    no previously-included directories found matching 'docs/_build'
    no previously-included directories found matching 'contrib'
    no previously-included directories found matching 'tasks'
    no previously-included directories found matching 'tests'
    Adding pip 9.0.1 to easy-install.pth file
    Installing pip script to /usr/local/bin
    Installing pip2.7 script to /usr/local/bin
    Installing pip2 script to /usr/local/bin
    
    Installed /Library/Python/2.7/site-packages/pip-9.0.1-py2.7.egg
    Processing dependencies for pip
    Finished processing dependencies for pip
    bash-3.2$ pip --version
    pip 9.0.1 from /Library/Python/2.7/site-packages/pip-9.0.1-py2.7.egg (python 2.7)
    

    find python packages in PyPI
    PyPI, python package index, has more than 100,000 python packages. Each package can be installed with two methods.

    • Install it with pip
    • bash-3.2$ pip install package_name
      
    • Download the tarball, unpack, and then install it
    • bash-3.2$ python setup.py install
      

    basic pip commands

    • list installed packages
    • bash-3.2$ pip list
      
    • install packages
    • bash-3.2$ pip install package_name
      
    • uninstall packages
    • bash-3.2$ pip uninstall package_name
      

    conclusion
    The post shows how to intall pip, how to find python packages, and basic pip commands.

    nodejs: npm

    July 31, 2017

    The post discusses npm.

    environment

    bash-3.2$ sw_vers
    ProductName:    Mac OS X
    ProductVersion: 10.11.6
    BuildVersion:   15G1510
    

    what is npm
    Package manager of nodejs

    how to install it
    It is installed automatically after nodejs is installed.

    bash-3.2$ brew install node
    bash-3.2$ node -v
    v8.1.4
    bash-3.2$ npm -v
    5.0.3
    

    conclusion
    The post notes npm.

    aws: ec2: ebs and instance store

    July 30, 2017

    The post discusses ebs and instance store.

    what is a ec2 instance
    A running virtual machine in aws cloud.

    instance and root device volume
    Instances can be categorised into two groups according to their root device volume.

    • A ebs-backed instance is a running machine whose image is stored at ebs
    • A instance store-backed instance is a running machine whose image is stored at instance store
      • what is ebs
        EBS is an aws service. It stands for elastic block service.

        • Similar to s3, ebs is also a storage service. But it is only for image of ec2 instance.
        • The data in ebs is persistent even its corresponding instance is stopped.
        • The charge of ebs is additional. It is not included within instance’s hourly running cost.
        • When a instance is stopped, its corresponding ebs is still in use and charged.
        • When a instance is terminated, its instance is deleted. If the instance is ebs-backed, the ebs is also deleted at which time the ebs is stopped charged

        what is instance store
        A storage within the instance itself.

        • The physical storage of instance store is attached to the host computer.
        • The instance store could have many instance store volumes. Each instance volume could be represented as linux device, such as /dev/eupheumeral0, /dev/eupheumeral1, and so on.
        • The data in instance store is lost when its corresponding instance is stopped
        • The charge of instance store is included within instance’s hourly running cost.

        conclusion
        If persistent data is required, then choose ebs-backed instance type. But be careful that the ebs is still charged when its corresponding instance is stopped. Only when the instance is terminated does the ebs stop been charged.

        reference
        Amazon EC2 Root Device Volume
        Amazon EC2 Instance Store

    aws: ec2: instance type

    July 30, 2017

    The post discusses ec2 instance and instance type.

    what is a ec2 instace
    A running ec2 instance is a virtual machine running in the aws cloud service.

    instance types
    Before a machine is running, we could decide which image to run on which machine. In aws ec2 context, we could choose which ami(Amazon machine image) to run on which instance type. In this analogy, choosing instance type is identical to choosing the machine on which the image is running.

    more related to instance types
    ec2 supports lots of instance types.

    • Instance types could be categorised into general, compute, memory, storage, and accelerated computing.
    • Each instance type category includes similar instance types with different power. For example, general purpose instance types have t2.nano, t2.micro, t2.small, t2.medium, t2.large and, t2.xlarge. As expected t2.micro is more powerful and expensive than t2.nano, t2.small is more powerful and expensive than t2.micro.
    • t2.micro is the only free tier eligible instance type.

    conclusion
    A brief note of ec2 instance type.

    reference
    Instance Types

    nodejs: mongoose module and mongodb

    July 27, 2017

    The post shows how a nodejs program connects to mongoDB with mongoose module.

    version

    bash-3.2$ node -v
    v8.1.4
    

    init nodejs project

    bash-3.2$ npm init
    This utility will walk you through creating a package.json file.
    It only covers the most common items, and tries to guess sensible defaults.
    
    See `npm help json` for definitive documentation on these fields
    and exactly what they do.
    
    Use `npm install <pkg>` afterwards to install a package and
    save it as a dependency in the package.json file.
    
    Press ^C at any time to quit.
    package name: (myapp) 
    version: (1.0.0) 
    description: 
    entry point: (index.js) app.js
    test command: 
    git repository: 
    keywords: 
    author: 
    license: (ISC) 
    About to write to /Users/chengyihe/workspace/node/myapp/package.json:
    
    {
      "name": "myapp",
      "version": "1.0.0",
      "description": "",
      "main": "app.js",
      "scripts": {
        "test": "echo \"Error: no test specified\" && exit 1"
      },
      "author": "",
      "license": "ISC"
    }
    
    
    Is this ok? (yes) 
    

    install mongoose module
    By default, npm install modules locally rather than globally. The files related to mongoose module is put under $(pwd)/node_modules directory.

    bash-3.2$ npm install mongoose
    npm notice created a lockfile as package-lock.json. You should commit this file.
    npm WARN myapp@1.0.0 No description
    npm WARN myapp@1.0.0 No repository field.
    
    + mongoose@4.11.4
    added 31 packages in 6.164s
    bash-3.2$ ls -l node_modules/
    total 0
    drwxr-xr-x   82 chengyihe  staff   2788 Jul 27 07:20 async
    drwxr-xr-x    7 chengyihe  staff    238 Jul 27 07:20 bluebird
    drwxr-xr-x   10 chengyihe  staff    340 Jul 27 07:20 bson
    drwxr-xr-x    6 chengyihe  staff    204 Jul 27 07:20 buffer-shims
    drwxr-xr-x    8 chengyihe  staff    272 Jul 27 07:20 core-util-is
    drwxr-xr-x   15 chengyihe  staff    510 Jul 27 07:20 debug
    drwxr-xr-x    8 chengyihe  staff    272 Jul 27 07:20 es6-promise
    drwxr-xr-x    9 chengyihe  staff    306 Jul 27 07:20 hooks-fixed
    drwxr-xr-x    7 chengyihe  staff    238 Jul 27 07:20 inherits
    drwxr-xr-x   10 chengyihe  staff    340 Jul 27 07:20 isarray
    drwxr-xr-x   12 chengyihe  staff    408 Jul 27 07:20 kareem
    drwxr-xr-x  640 chengyihe  staff  21760 Jul 27 07:20 lodash
    drwxr-xr-x   17 chengyihe  staff    578 Jul 27 07:20 mongodb
    drwxr-xr-x   23 chengyihe  staff    782 Jul 27 07:20 mongodb-core
    drwxr-xr-x   18 chengyihe  staff    612 Jul 27 07:20 mongoose
    drwxr-xr-x   16 chengyihe  staff    544 Jul 27 07:20 mpath
    drwxr-xr-x   10 chengyihe  staff    340 Jul 27 07:20 mpromise
    drwxr-xr-x   12 chengyihe  staff    408 Jul 27 07:20 mquery
    drwxr-xr-x    6 chengyihe  staff    204 Jul 27 07:20 ms
    drwxr-xr-x   12 chengyihe  staff    408 Jul 27 07:20 muri
    drwxr-xr-x    8 chengyihe  staff    272 Jul 27 07:20 process-nextick-args
    drwxr-xr-x   19 chengyihe  staff    646 Jul 27 07:20 readable-stream
    drwxr-xr-x   11 chengyihe  staff    374 Jul 27 07:20 regexp-clone
    drwxr-xr-x   10 chengyihe  staff    340 Jul 27 07:20 require_optional
    drwxr-xr-x    6 chengyihe  staff    204 Jul 27 07:20 resolve-from
    drwxr-xr-x    8 chengyihe  staff    272 Jul 27 07:20 safe-buffer
    drwxr-xr-x    8 chengyihe  staff    272 Jul 27 07:20 semver
    drwxr-xr-x    7 chengyihe  staff    238 Jul 27 07:20 sliced
    drwxr-xr-x    7 chengyihe  staff    238 Jul 27 07:20 string_decoder
    drwxr-xr-x    8 chengyihe  staff    272 Jul 27 07:20 util-deprecate
    

    mongodb client source code
    The nodejs example loads mongoose module, connects to a mongoDB server, and then inserts a data satisfied a schema.

    • require(‘mongoose’): it loads mongoose module
    • mongoose.connect(): it connects to a database in a mongoDB server
    • Schema: specify the data structure of document in collection
    • Model: it corresponds to a collection in the connected mongoDB server. The first parameter specifies the collection name, the second one is a schema which specifies the format of documents within the collection
    bash-3.2$ cat app.js 
    var mongoose = require('mongoose');
    mongoose.connect('mongodb://localhost/test', {useMongoClient: true,})
    
    var Schema = mongoose.Schema
    var memberSchema = new Schema(
        {
            name: String
        }
    )
    var member = mongoose.model('member', memberSchema)
    var person = new member({ name: 'chengyihe' })
    
    person.save(function (err) {
        if (err) {
            console.log(err);
        } else {
            console.log('saved');
        }
    });
    

    output of running the mongodb client
    Output shows data is saved in mongoDB server successfully.

    bash-3.2$ node app.js
    (node:54460) DeprecationWarning: Mongoose: mpromise (mongoose's default promise library) is deprecated, plug in your own promise library instead: http://mongoosejs.com/docs/promises.html
    saved
    

    use mongodb shell to check the result
    It shows that the test database’s members collection has a document which is inserted by above example.

    bash-3.2$ mongo
    MongoDB shell version v3.4.6
    connecting to: mongodb://127.0.0.1:27017
    MongoDB server version: 3.4.6
    Server has startup warnings:
    2017-07-26T20:43:13.356+0800 I CONTROL  [initandlisten]
    2017-07-26T20:43:13.357+0800 I CONTROL  [initandlisten] ** WARNING: Access control is not enabled for the database.
    2017-07-26T20:43:13.357+0800 I CONTROL  [initandlisten] **          Read and write access to data and configuration is unrestricted.
    2017-07-26T20:43:13.357+0800 I CONTROL  [initandlisten]
    2017-07-26T20:43:13.357+0800 I CONTROL  [initandlisten]
    2017-07-26T20:43:13.357+0800 I CONTROL  [initandlisten] ** WARNING: soft rlimits too low. Number of files is 256, should be at least 1000
    > db.kernels.drop()
    true
    > show collections
    members
    > db.members.find()
    { "_id" : ObjectId("597936a8cff68dd4bc0b4c71"), "name" : "chengyihe", "__v" : 0 }
    > 
    

    conclusion
    The post uses a nodejs with mongoose module to insert data in a mongoDB server. Then, it query the data with mongoDB shell.

    mongodb: find(), limit() and skip()

    July 26, 2017

    The post shows how to use limit() and skip() to partial shows data.

    version

    bash-3.2$ mongo
    MongoDB shell version v3.4.6
    connecting to: mongodb://127.0.0.1:27017
    

    show all documents

    > db.member.find()
    { "_id" : ObjectId("5978cda6558e820054f7be9c"), "name" : "chengyihe" }
    { "_id" : ObjectId("5978cdac558e820054f7be9d"), "name" : "woody" }
    { "_id" : ObjectId("5978cdaf558e820054f7be9e"), "name" : "max" }
    { "_id" : ObjectId("5978cdb2558e820054f7be9f"), "name" : "daniel" }
    

    show the first two documents

    > db.member.find().limit(2)
    { "_id" : ObjectId("5978cda6558e820054f7be9c"), "name" : "chengyihe" }
    { "_id" : ObjectId("5978cdac558e820054f7be9d"), "name" : "woody" }
    

    after skipping the first document, show the first two documents

    > db.member.find().limit(2).skip(1)
    { "_id" : ObjectId("5978cdac558e820054f7be9d"), "name" : "woody" }
    { "_id" : ObjectId("5978cdaf558e820054f7be9e"), "name" : "max" }
    

    conclusion
    The post shows some example to demonstrate the functionality of limit() and skip().

    mongodb: find and projection

    July 26, 2017

    This post discusses find and projection in mongoDB.

    version

    bash-3.2$ mongo
    MongoDB shell version v3.4.6
    connecting to: mongodb://127.0.0.1:27017
    

    insert document into a collection
    Add four documents into test.member collection.

    > show dbs
    admin  0.000GB
    local  0.000GB
    > db
    test
    > db.member.insert({name: 'chengyihe'})
    WriteResult({ "nInserted" : 1 })
    > db.member.insert({name: 'woody'})
    WriteResult({ "nInserted" : 1 })
    > db.member.insert({name: 'max'})
    WriteResult({ "nInserted" : 1 })
    > db.member.insert({name: 'daniel'})
    WriteResult({ "nInserted" : 1 })
    

    show documents in a collection with projection

    • db.member.find() list all documents with all fields.
    • db.member.find({},{_id: 0, name: 1}) list all documents with only name field.
    • > db.member.find()
      { "_id" : ObjectId("5978cda6558e820054f7be9c"), "name" : "chengyihe" }
      { "_id" : ObjectId("5978cdac558e820054f7be9d"), "name" : "woody" }
      { "_id" : ObjectId("5978cdaf558e820054f7be9e"), "name" : "max" }
      { "_id" : ObjectId("5978cdb2558e820054f7be9f"), "name" : "daniel" }
      > db.member.find({},{_id: 0, name: 1})
      { "name" : "chengyihe" }
      { "name" : "woody" }
      { "name" : "max" }
      { "name" : "daniel" }
      

      conclusion
      The post shows how to use projection operator to show only some fields of satisfied documents.


    %d bloggers like this: